package stackdemo;

import java.util.Arrays;
import java.util.Stack;

public class MyStack {
    public int[] elem;
    public int usedSize;

    public MyStack() {
        elem = new int[10];
    }

    //入栈
    public void push(int val) {
        //1.如果满了进行扩容
        if (isFull()) {
            elem = Arrays.copyOf(elem, elem.length * 2);
        }
        //2.入栈
        elem[usedSize] = val;
        //3.usedSize++;
        usedSize++;
    }

    //判满
    public boolean isFull() {
        return usedSize == elem.length;
    }

    //弹出并删除
    public int pop() {
        if (isEmpty()) {
            return -1;//最好加个异常
        }
        int oldVal = elem[usedSize - 1];
        usedSize--;
        return oldVal;
    }

    //判空
    public boolean isEmpty() {
        return usedSize == 0;
    }

    //获取栈顶数据
    public int peek() {
        if (isEmpty()) {
            return -1;//最好加个异常
        }
        return elem[usedSize - 1];
    }

    //求长度
    public int getUsedSize() {
        return usedSize;
    }

    //括号匹配
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else {
                if (stack.empty()) return false;
                char topL  = stack.peek();
                if (topL == '(' && ch == ')' || topL == '{' && ch == '}'
                || topL == '[' && ch == ']') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if (!stack.empty()) {
            return false;
        }
        return true;
    }

    //逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < tokens.length; i++) {
            String tmp = tokens[i];
            if (!isOperation(tmp)) {
                stack.push(Integer.parseInt(tmp));
            } else {
                Integer val2 = stack.pop();
                Integer val1 = stack.pop();
                switch (tmp) {
                    case "+":
                        stack.push(val1 + val2);
                        break;
                    case "-":
                        stack.push(val1 - val2);
                        break;
                    case "*":
                        stack.push(val1 * val2);
                        break;
                    case "/":
                        stack.push(val1 / val2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    private boolean isOperation(String tmp) {
        if (tmp.equals("+") || tmp.equals("-") || tmp.equals("*")
                || tmp.equals("/")) {
            return true;
        }
        return false;
    }
}



